#!/usr/bin/env python

"""
- Remember to change the above line to fit your environment
- Python >= 2.5 is required
- Read the LICENSE file before redistributing/modifying this software
"""

"""
Data structures
"""
class Element:
    """
    Defines an element, i.e. the basic unit of a working list, holding both
    a state and left of (left) counters
    """
    left = None
    state = None

    def __init__(self, state, left):
        self.state = state
        self.left = left

    def __repr__(self):
        return '<' + self.state + ', ' + str(tuple(self.left)) + '>'

    def clone(self):
        return Element(str(self.state), [x for x in self.left])

    def exists_match(self, other):
        for l in self.left:
            for o in other:
                if l == o:
                    return True
        return False

    def all_match(self, other):
        if len(other) != len(self.left):
            return False
        for i in range(len(self.left)):
            if self.left[i] != other[i]:
                return False
        return True

    def inc(self, u, C):
        for c in C.cliques_of(u):
            self.left[c] += 1

class Decisor:
    """
    This class' run() method implement the membership problem decisor.
    """
    def __init__(self, string, automaton, covering, code_profiling = False, backsize = -1, verbose = False, latex_report = False, latex_open = True, latex_close = True, simulation_id = 1):
        self.code_profiling = code_profiling
        self.string = string
        self.automaton = automaton
        self.covering = covering
        self.verbose = verbose
        self.backsize = backsize
        self.latex_open = latex_open
        self.latex_close = latex_close
        self.latex = latex_report
        self.simulation_id = simulation_id
        self.latex_content = '\\section{Simulation %d}'%self.simulation_id

        if self.code_profiling:
            self.run_and_profile()
        else:
            self.run()
        
    def subset_found(self, needle_set, other_sets):
        """
        (DEPRECATED) Tests whether 'needle_set' is subset of any of the 'other_sets'
        """
        for s in other_sets:
            if needle_set.issubset(s) or s.issubset(needle_set):
                return s

        return None

    def on_all_heads(self, u, C, L, Q):
        """
        Test whether 'u' is on the head of its queues
        """
        for c in C.cliques_of(u):
            if u != Q[c][L[c]]:
                return False
        return True

    def run_and_profile(self):
        import cProfile, pstats
        pr = cProfile.Profile()
        pr.runcall(self.run)
        st = pstats.Stats(pr)
        if self.verbose:
            st.print_stats()
        self.statistics = {
            'time': st.total_tt,
            'coversize': len(self.covering),
            'strlen': len(self.string),
            'backsize': self.backsize,
            'sigmasize': len(self.covering.sigma),
            'alpha': self.covering.alpha
            }

    def run(self):
        """
        This is the core algorithm implementation
         - U: the string (it must be a list() object of strings/characters. E.g., list('1', '2', '12, '3', '5'))
         - A: the automaton (it must be an instance of fsm.FSM)
         - C: the clique covering (it must be an instance of covering.Covering)
        """

        """
        Definitions
        """
        A = self.automaton
        C = self.covering
        U = self.string

        E, E_next = [], [] # The set of element to be processed (and the next one)
        R = [] # The right counters
        L = [] # The left counters
        Q = [[] for i in range(len(C))] # A queue set for storing symbols
        M = {} # Needed to take notes of existing elements
        closed = False
        blocked = False
        i = 0 # Loop counter

        """
        Initializations
        """
        for r in range(len(C)): R.append(0)
        for r in range(len(C)): L.append(0)
        E = [Element(A.initial, L)]

        """
        Printing stuff
        """
        if self.verbose:
            print '+----------------------------------------------------------------------------------------------------------+'
            print '| U: %s'%U
            print '| A: %s'%A
            print '| R: %s'%R
            print '| Q: %s'%Q
            print '| E: %s'%E
            print '| C: %s'%C
            print '+----------------------------------------------------------------------------------------------------------+'
            print

        if self.latex:
            self.latex_content += '\\paragraph{Automaton}'
            self.latex_content += '\\begin{center}'
            self.latex_content += '\\includegraphic[width=\\textwidth]{automaton_%d}'%self.simulation_id
            self.latex_content += '\\end{center}'
            self.latex_content += '\\paragraph{String}'
            self.latex_content += '\\begin{center}'
            self.latex_content += ' '.join(U)
            self.latex_content += '\\end{center}'
            self.latex_content += '\\begin{enumerate}'

        """
        Core algorithm
        """
        while i < 2 * len(U):
            if self.verbose:
                print 'ITERATION #%d'%i
            if self.latex:
                self.latex_content += '\\item Execution\n'
                
            E_next = []

            """
            Buffering step (while the reading cursor has something to read)
            """
            if i < len(U):
                for c in C.cliques_of(U[i]):
                    Q[c].append(U[i])
                    R[c] = R[c] + 1
            """
            END of buffering step
            """

            if self.verbose:
                print 'Q = ', Q
                print 'E = ', E
                print 'M = ', M

            """
            Processing step
            """
            for e in E:
                if self.verbose:
                    print '+---------------------------------------------------+'
                    print '| Current element: ' + str(e)
                    print '+---------------------------------------------------+'
                    print 'Phase 1:'
                    print '\tR = ', R

                # Test whether the element could evolve; if 'yes', copy it for further processing
                if self.verbose:
                    print '\t* e.exists_match(R) =', e.exists_match(R)
                if e.exists_match(R):
                    if self.verbose:
                        print '(at least one match found)'
                    E_next.append(e.clone())
                    if self.verbose:
                        print '\t', e, 'copied'

                if self.verbose:
                    print 'Phase 2:'

                """
                Queue processing
                """
                for l in range(len(e.left)):
                    if self.verbose:
                        print '\tClique #%d %s'%(l, C.clique(l))
                    # If there is something to read in the element's queue
                    if e.left[l] < R[l]:
                        u = Q[l][e.left[l]] #hold the symbol under the element's queue's left cursor
                        if self.verbose:
                            print '\t\t*', u, 'is under the cursor'
                        if A.can_read(u, e.state): #and check whether it's readable according to the automaton
                            if self.verbose:
                                print '\t\t\t-', u, 'is readable'
                            if self.on_all_heads(u, C, e.left, Q): #also check whether the symbol is on all involved queue's head
                                if self.verbose:
                                    print '\t\t*', u, 'is on all heads'
                                e_next = e.clone()
                                e_next.state = A.get_transition(e.state, u)
                                e_next.inc(u, C) #increment each left counter according to the involved queues
                                
                                if e_next.state in A.finals:
                                    if e_next.all_match(R):
                                        self.decision = True
                                        return self.decision
                                #pseudo-else
                                found = True
                                try:
                                    M[(e_next.state, tuple(e_next.left))]
                                except KeyError:
                                    found = False
                                if not found and e_next.exists_match(R):
                                    if self.verbose:
                                        print '\t\t*', e_next, 'appended'
                                    E_next.append(e_next)
                                    M[(e_next.state, tuple(e_next.left))] = True
                                else:
                                    if self.verbose:
                                        print '\t\t*', e_next, 'NOT appended:'
                                        print '\t\t\t* e_next.state in A.finals =', e_next.state in A.finals
                                        print '\t\t\t* e_next.exists_match(R) =', e_next.exists_match(R)
                                        
                """
                END of queue processing
                """
            """
            END of processing step
            """

            i += 1
            E = E_next
            E_next = []
            if self.verbose:
                print 'i = ', i
                print 'E = ', E
                print
                print '====================================================='
                print
        
        self.decision = closed
        return self.decision

    def latex_results(self):
        if self.latex_open:
            code = '\\documentclass[10pt]{scrartcl}\n\n'
            code += '\\usepackage{graphicx}\n\n'        
            code += '\\begin{document}\n\n'

        code += self.latex_content

        if self.latex_close:
            code += '\n\n\\end{document}\n'
        return code        


def main():
    E = Element('q7', [1, 1, 1, 1, 1, 1, 1, 0, 0, 0])
    E_copy = E.clone()
    print id(E)
    print id(E_copy)
    print E
    print E_copy
    E_copy.state = 'q10'
    print E
    print E_copy
    E_copy.left[3] += 2
    print E
    print E_copy
    EE = [E, E_copy]
    FF = EE
    EE = []
    print FF
    print EE
    #print E.exists_match([1, 1, 1, 1, 1, 1, 1, 1, 0, 0])

if __name__ == '__main__':
    main()
